﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace AlgorithmThinks.DynamicProgramming
{
    /// <summary>
    /// 最长公共子序列
    /// </summary>
    public class LongestCommonSequence
    {
        public static string Action1(string s1,string s2)
        {
            if (s1.Last() == s2.Last())
            {
               return Action1(s1.Remove(s1.Length - 1), s2.Remove(s2.Length - 1));
            }
            else
            {
                return compareLength(Action1(s1.Remove(s1.Length - 1), s2),Action1(s1, s2.Remove(s2.Length - 1)));
            }
        }

        public static string compareLength(string s1,string s2)
        {
            if (s1.Length > s2.Length)
            {
                return s1;
            }

            return s2;
        }




        //求解str1 和 str2 的最长公共子序列
        public static int LCS(String str1, String str2)
        {
            int[,] c = new int[str1.Length + 1, str2.Length + 1];
            for (int row = 0; row <= str1.Length; row++)
                c[row, 0] = 0;
            for (int column = 0; column <= str2.Length; column++)
                c[0, column] = 0;

            for (int i = 1; i <= str1.Length; i++)
                for (int j = 1; j <= str2.Length; j++)
                {
                    if (str1[i - 1] == str2[j - 1])
                        c[i, j] = c[i - 1, j - 1] + 1;
                    else if (c[i, j - 1] > c[i - 1, j])
                        c[i, j] = c[i, j - 1];
                    else
                        c[i, j] = c[i - 1, j];
                }
            return c[str1.Length, str2.Length];
        }



    }
}
